package Sequence;


import java.util.Arrays;

public class Test0416 {
    public static void main(String[] args) {
        new Solution0416_2().canPartition(new int[]{1,2,5});
    }
}



class Solution0416_1 {
    public boolean canPartition(int[] nums) {
        int length = nums.length;
        if (length <=1) return false;
        int sum = 0;
        for (int num : nums) sum += num;
        if ((sum&1)== 1) return false;
        int target = sum>>1;

        boolean[] dp = new boolean[target+1];
        dp[0]=true;

        for (int num:nums) {
            if (dp[target]) return true;
            for (int j = target; j>num; j--)
                dp[j]=dp[j]||dp[j-num];

            if (num <target) dp[num] = true;
            else return num == target;
        }


        return dp[target];
    }
}

class Solution0416_2 {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;
        if ((sum&1)==1) return false;
        int target = sum>>1;

        boolean[] dp1 = new boolean[target+1];
        boolean[] dp2 = new boolean[target+1];
        dp1[0]=true;
        dp2[0]=true;
        for (int num : nums) {
            for (int i = 0; i < dp1.length; i++) {
                if (dp1[i]) {
                    if (i+num<=target)
                        dp2[i+num]=true;
                    dp2[i]=true;
                }
            }
            boolean[] temp = dp2;
            dp2 = dp1;
            dp1 = temp;
            if (dp1[target]) return true;
        }
        return false;
    }
}
